package graphesTOTEST;

/** Classe qui implante l'algorithme "du plus court chemin" de
 * WarshallFloyd : calcul du chemin de poid minimal entre 2 sommets
 * donnés du graphe. Le graphe ne doit pas contenir de cycle de poid
 * strictement négatif (dont la somme des arcs est strictement
 * négative), par contre un arc peut avoir un poid négatif). 
 *
 * @author un client anonyme
*/
public class WarshallFloyd {
	
    /** graphe d'entrée. */
	public Graphe gPlus;
    /** R[i][j] indique le poid du chemin minimal entre i et j, 
	Graphe.ALPHA_NOTDEF si pas de chemin. */
	public int R[][];
	
	public WarshallFloyd(Graphe g) {
		gPlus = new Graphe(g);
		R     = new int[gPlus.NMAX][gPlus.NMAX];
	}
	
	private void initRoutage() {
	 	for (int i=0; i<gPlus.NMAX; i++) {
	 		for (int j=0; j<gPlus.NMAX; j++) {
		 		if (gPlus.existeArc(i,j))
		 			R[i][j] = i;
		 		else 
		 			R[i][j] = Graphe.ALPHA_NOTDEF;
	 		}
 		}		 		
	}
	

    /** Calcule la matrice R des chemins de poid minimum pour le graphe g. */
    public void fermetureEtRoutage() {
    	    	
	    int v1,v2,w;
	    initRoutage();
	    
    	
    	for (int x=0; (x<gPlus.NMAX); x++) {
        	for (int y=0; (y<gPlus.NMAX); y++) {
	        	if (gPlus.existeArc(y,x)) {
					v1 = gPlus.getValArc(y, x);					        						
        			for(int z=0; (z<gPlus.NMAX); z++) {
	        			
	        			if (gPlus.existeArc(x,z)) {
	        				v2 = gPlus.getValArc(x, z);	        		
	        				if (gPlus.existeArc(y,z)) {
		        				w = gPlus.getValArc(y, z);
		        				if (v1+v2 < w) {
			        				gPlus.setValArc(y,z,v1+v2);
			        				R[y][z] = R[x][z];
		        				}
	        				}
	        				else {
			        			gPlus.ajoutArc(y,z,v1+v2);		        				
			        			R[y][z] = R[x][z];
	        				}
        				} //existeArc(x,z)
        				
        			} //for z
        		} //existeArc (y,x)
        	} //For y
    	} //For x
    	
    	    	
    }
    
    public void afficheChemin(int i, int j) {
	    if (i==j) {
		    System.out.println("WarshallFloyd::afficheChemin: ["+i+"]");
	    }
	   	if (!gPlus.existeArc(i,j)) {
		    System.out.println("WarshallFloyd::afficheChemin: Il n'existe pas de chemin de "+i+" à "+j);
	    }
	    else {
		    System.out.print("WarshallFloyd::afficheChemin: ");
		    System.out.print("[");
		    afficheCheminRec(i,j);
		    System.out.println("]");
	    }		   	
    }
    
    public void afficheCheminRec(int i, int j) {
	    if (i==j) {
		    System.out.print(i);
	    }
		else {
			afficheCheminRec(i, R[i][j]);
		    System.out.print(" , "+j);
	    }
    }
    				     
	
} //Classe WarshallFloyd